package 滑动窗口;


import java.util.Arrays;

/**
 * 从局部最优到全局最优的思想出发，我们抓住题目中最重要的一条信息
 * 即：都为小写字母！
 * 那么我们就可以求得，1个字符情况下最大长度，2个字符下最大长度...26个字符下最大长度
 * 从而找那个最大的长度。
 * 滑动窗口 + 双指针
 */
public class LeetCode395_至少有K个重复字符的最长字串 {
    public int longestSubstring(String s, int k) {
        int ans = 0;
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] cnt = new int[26];
        for (int c = 1; c <= 26; c++) {
            // 没循环一次就要初始化数组每个字母个数为0
            Arrays.fill(cnt,0);
            // tot代表[j,i]区间所有的字符种类数量;
            //sum代表满足「出现次数不少于 k」的字符种类数
            for (int i = 0, j = 0, tot = 0, sum = 0;i < n; i++) {
                int u = cs[i] - 'a';
                cnt[u] ++;
                // 如果第一次添加字符，说明字符的种类数+1
                if(cnt[u] == 1) tot++;
                // 如果添加到的字符数量等于k，说明该字符从不达标变为达标，达标数+1
                if(cnt[u] == k) sum++;
                // 当区间所包含的字符种类数量tot超过了当前的限定的总字符数c，
                // 那么久被迫需要删掉一些字符了，而删除方法只能时滑动窗口左指针右移
                while (tot > c) {
                    int t = cs[j++] - 'a';
                    cnt[t] --;
                    // 如果减少到的字符数量变为0，说明总字符种类-1
                    if(cnt[t] == 0) tot--;
                    // 如果减少后的这个字符数量为k-1，说明原来它是达标字符，现在变成了不达标
                    if(cnt[t] == k-1) sum--;
                }
                // 现有数组的所有字符都达标，也就是每一个字符都成为达标字符
                if(tot == sum) ans = Math.max(ans, i - j + 1);
            }
        }
        return ans;
    }
}
